//二叉搜索树中的两个节点被错误地交换。 
//
// 请在不改变其结构的情况下，恢复这棵树。 
//
// 示例 1: 
//
// 输入: [1,3,null,null,2]
//
//   1
//  /
// 3
//  \
//   2
//
//输出: [3,1,null,null,2]
//
//   3
//  /
// 1
//  \
//   2
// 
//
// 示例 2: 
//
// 输入: [3,1,4,null,null,2]
//
//  3
// / \
//1   4
//   /
//  2
//
//输出: [2,1,4,null,null,3]
//
//  2
// / \
//1   4
//   /
//  3 
//
// 进阶: 
//
// 
// 使用 O(n) 空间复杂度的解法很容易实现。 
// 你能想出一个只使用常数空间的解决方案吗？ 
// 
// Related Topics 树 深度优先搜索 
// 👍 256 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;
import common.util.MyUtil;

/**
 * Java：恢复二叉搜索树
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P99_RecoverBinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new P99_RecoverBinarySearchTree().new Solution();
        int[] nums = MyUtil.createArray(1, 2, 3, 8, 5, 6, 7, 4, 9);
        // 判断交换的两个元素
        Integer i1 = null, i2 = null;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                i2 = nums[i];
                if (i1 == null) {
                    i1 = nums[i - 1];
                } else {
                    break;
                }
            }
        }
        MyUtil.print(i1 + "," + i2);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * 一次遍历
     * 时间复杂度 最好 O(1) 最坏 O(n)
     * 空间复杂度 O(n)
     */
    class Solution {
        TreeNode t1 = null, t2 = null, pre = null;

        public void recoverTree(TreeNode root) {
            // 找出 t1 t2
            traverseTree(root);
            // 交换值
            t1.val = t1.val + t2.val;
            t2.val = t1.val - t2.val;
            t1.val = t1.val - t2.val;
        }

        private void traverseTree(TreeNode root) {
            if (root == null) {
                return;
            }
            traverseTree(root.left);
            if (pre != null && root.val < pre.val) {
                t1 = root;
                if (t2 == null) {
                    t2 = pre;
                } else {
                    return;
                }
            }
            pre = root;
            traverseTree(root.right);
        }

    }

    ///**
    // * 时间复杂度 O(n)
    // * 空间复杂度 O(n)
    // */
    //class Solution {
    //    public void recoverTree(TreeNode root) {
    //        List<Integer> nums = new ArrayList<>();
    //        // 中序遍历得到值列表
    //        traverseTree1(root, nums);
    //        // 判断交换的两个元素
    //        Integer i1 = null, i2 = null;
    //        for (int i = 1; i < nums.size(); i++) {
    //            if (nums.get(i) < nums.get(i - 1)) {
    //                i1 = nums.get(i);
    //                if (i2 == null) {
    //                    i2 = nums.get(i - 1);
    //                } else {
    //                    break;
    //                }
    //            }
    //        }
    //        // 值替换
    //        traverseTree2(root, i1, i2);
    //    }
    //
    //    private void traverseTree1(TreeNode root, List<Integer> nums) {
    //        if (root == null) {
    //            return;
    //        }
    //        traverseTree1(root.left, nums);
    //        nums.add(root.val);
    //        traverseTree1(root.right, nums);
    //    }
    //
    //    private void traverseTree2(TreeNode root, int i1, int i2) {
    //        if (root == null) {
    //            return;
    //        }
    //        traverseTree2(root.left, i1, i2);
    //        if (root.val == i1 || root.val == i2) {
    //            root.val = root.val == i1 ? i2 : i1;
    //        }
    //        traverseTree2(root.right, i1, i2);
    //    }
    //}
    //leetcode submit region end(Prohibit modification and deletion)

}
